package com.ls.que91_95;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：ls
 * @date ：2022/3/11 9:54
 * @description：...
 */
public class RestoreIpAddresses {
    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        char[] ip = s.toCharArray();
        for (int i=1; i<=3;i++){
            tmp.add(i);
            ip_recur(ip, 0, i, 1, tmp, res);
            tmp.remove(0);
        }
        return res;
    }

    public static int getnum(char[] ip, int start, int len){
        int sum=0, m = 1;
        while (len>0){
            len-=1;
            sum += (ip[start+len] - '0') * m;
            m*=10;
        }
        return sum;
    }

    public static void ip_recur(char[] ip, int start, int len, int index, List<Integer> tmp, List<String> res){
        // 超过了
        if (start+len > ip.length)
            return;
        // 前置0
        if (len!=1 && ip[start] == '0')
            return;
        // 有剩余
        if (index == 4 && start+len != ip.length)
            return;
        int num = getnum(ip,start,len);
        // 数字大小超过了255
        if (num > 255)
            return;
        if (index == 4){    // 正确的一种结果
            String s = new String(ip).substring(0, tmp.get(0));

            for (int j=1; j<tmp.size();j++){
                s += '.' + new String(ip).substring(tmp.get(j-1), tmp.get(j));
            }
            res.add(s);
        }else{ // 继续递归
            for (int i=1; i<=3; i++){
                tmp.add(start+len + i);
                ip_recur(ip, start+len, i, index+1, tmp, res);
                tmp.remove(tmp.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        List<String> res = restoreIpAddresses("101023");
        for (String s : res)
            System.out.println(s);
    }
}
